//
// Created by Administrator on 2021/4/30.
//

/*
你一个整数数组nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。


示例 1：

输入：nums = [2,2,3,2]
输出：3
示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99


提示：

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <vector>
#include <iostream>
#include <climits>
#include <unordered_map>

using namespace std;

class Solution {
public:
    /**
     * 1、对所有出现的数字进行计数 返回数量为1的
     * 2、位运算（还没想到怎么做）
     * @param nums
     * @return
     */
    int singleNumber(vector<int> &nums) {
        unordered_map<int, int> counter;
        for (const auto &num:nums) {
            ++counter[num];
        }
        int ans = 0;
        for (const auto &num:counter) {
            if (num.second == 1) {
                ans = num.first;
                break;
            }
        }
        return ans;
    }

    /** 题解 位运算
    为了方便叙述，我们称「只出现了一次的元素」为「答案」。

    由于数组中的元素都在 int（即 32 位整数）范围内，因此我们可以依次计算答案的每一个二进制位是 0 还是 1。

    具体地，考虑答案的第 i 个二进制位（i 从 0 开始编号），它可能为 0 或 1。对于数组中非答案的元素，
     每一个元素都出现了 3 次，对应着第 i 个二进制位的 3 个 0 或 3 个 1，无论是哪一种情况，
     它们的和都是 3 的倍数（即和为 0 或 3）。因此：

    答案的第 i 个二进制位就是数组中所有元素的第 i 个二进制位之和除以 3 的余数。

     这样一来，对于数组中的每一个元素 x，我们使用位运算 (x >> i) & 1得到 x 的第 i 个二进制位，并
     将它们相加再对 3 取余，得到的结果一定为 0 或 1，即为答案的第 i 个二进制位。
     */
    int singleNumber2(vector<int> &nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num: nums) {
                total += ((num >> i) & 1);  // 得到num的第i位
            }
            if (total % 3) {  // 对3取余如果得到1，就记录到结果上
                ans |= (1 << i);
            }
        }
        return ans;

    }

};

int main() {
    vector<int> v1{2, 2, 3, 2};
    vector<int> v2{0, 1, 0, 1, 0, 1, 99};
    Solution sol;
    cout << sol.singleNumber(v1) << endl;
    cout << sol.singleNumber2(v2) << endl;

}